<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no, minimal-ui">
  <meta name="renderer" content="webkit">
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="format-detection" content="telephone=no,email=no,adress=no">
  <!-- Color theme for statusbar -->
  <meta name="theme-color" content="#000000" />
  <!-- 强制页面在当前窗口以独立页面显示,防止别人在框架里调用页面 -->
  <meta http-equiv="window-target" content="_top" />
  
  
  <title>哈希表 | 金旭的个人博客</title>
  <meta name="description" content="哈希表又称为散列表，它可以通过把值直接映射到表中的位置来访问。这个函数叫做哈希函数。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。比较知名的散列函数MD5&#x2F;SHA。查找、删除和插入时间复杂度都为O(1)。 散列函数设计 折叠法：将数据项按照位数分为若干段，再讲几段">
<meta property="og:type" content="article">
<meta property="og:title" content="哈希表">
<meta property="og:url" content="http://sunjinxu99.gitee.io/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/index.html">
<meta property="og:site_name" content="金旭的个人博客">
<meta property="og:description" content="哈希表又称为散列表，它可以通过把值直接映射到表中的位置来访问。这个函数叫做哈希函数。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。比较知名的散列函数MD5&#x2F;SHA。查找、删除和插入时间复杂度都为O(1)。 散列函数设计 折叠法：将数据项按照位数分为若干段，再讲几段">
<meta property="article:published_time" content="2020-03-26T06:54:57.263Z">
<meta property="article:modified_time" content="2021-07-06T15:37:46.589Z">
<meta property="article:author" content="金旭">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
  <!-- Canonical links -->
  <link rel="canonical" href="http://sunjinxu99.gitee.io/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/index.html">
  
    <link rel="alternate" href="/atom.xml" title="金旭的个人博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png" type="image/x-icon">
  
  
<link rel="stylesheet" href="/blog/css/style.css">

  
  
  
  
<meta name="generator" content="Hexo 4.2.0"></head>


<body class="main-center theme-blue# 主题颜色 theme-black theme-blue theme-green theme-purple" itemscope itemtype="http://schema.org/WebPage">
  <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  <div class="slimContent">
    <div class="navbar-header">
      
      
      <div class="profile-block text-center">
        <a id="avatar" href="" target="_blank">
          <img class="img-circle img-rotate" src="/blog/images/avatar.png" width="200" height="200">
        </a>
        <h2 id="name" class="hidden-xs hidden-sm">小马</h2>
        <h3 id="title" class="hidden-xs hidden-sm hidden-md"></h3>
        <small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> </small>
      </div>
      
      <div class="search" id="search-form-wrap">

    <form class="search-form sidebar-form">
        <div class="input-group">
            <input type="text" class="search-form-input form-control" placeholder="Search" />
            <span class="input-group-btn">
                <button type="submit" class="search-form-submit btn btn-flat" onclick="return false;"><i class="icon icon-search"></i></button>
            </span>
        </div>
    </form>
    <div class="ins-search">
  <div class="ins-search-mask"></div>
  <div class="ins-search-container">
    <div class="ins-input-wrapper">
      <input type="text" class="ins-search-input" placeholder="Type something..." x-webkit-speech />
      <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
    </div>
    <div class="ins-section-wrapper">
      <div class="ins-section-container"></div>
    </div>
  </div>
</div>


</div>
      <button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
    </div>
    <nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation">
      <ul class="nav navbar-nav main-nav ">
        
        
        <li class="menu-item menu-item-home">
          <a href="/blog/.">
            
            <i class="icon icon-home-fill"></i>
            
            <span class="menu-title">Home</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives">
            
            <i class="icon icon-archives-fill"></i>
            
            <span class="menu-title">Archives</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories">
            
            <i class="icon icon-folder"></i>
            
            <span class="menu-title">Categories</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-tags">
          <a href="/blog/tags">
            
            <i class="icon icon-tags"></i>
            
            <span class="menu-title">Tags</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-about">
          <a href="/blog/about">
            
            <i class="icon icon-cup-fill"></i>
            
            <span class="menu-title">About</span>
          </a>
        </li>
        
      </ul>
      
    </nav>
  </div>
</header>

  
    <aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    
      <div class="widget">
    <h3 class="widget-title">Board</h3>
    <div class="widget-body">
        <div id="board">
            <div class="content">
                <p>朝闻道夕死可矣</p>
            </div>
        </div>
    </div>
</div>

    
      
  <div class="widget">
    <h3 class="widget-title">Categories</h3>
    <div class="widget-body">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/JavaSE/">JavaSE</a><span class="category-list-count">7</span></li><li class="category-list-item"><a class="category-list-link" href="/blog/categories/LeetCode/">LeetCode</a><span class="category-list-count">3</span><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/LeetCode/%E7%AE%97%E6%B3%95/">算法</a><span class="category-list-count">3</span></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/blog/categories/%E6%9D%82%E8%AE%B0/">杂记</a><span class="category-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget-body tagcloud">
      <a href="/blog/tags/IO%E6%B5%81/" style="font-size: 13px;">IO流</a> <a href="/blog/tags/OSI%E5%8F%82%E8%80%83%E6%A8%A1%E5%9E%8B/" style="font-size: 13px;">OSI参考模型</a> <a href="/blog/tags/TCP-IP%E5%8F%82%E8%80%83%E6%A8%A1%E5%9E%8B/" style="font-size: 13px;">TCP/IP参考模型</a> <a href="/blog/tags/ftp%E5%8D%8F%E8%AE%AE/" style="font-size: 13px;">ftp协议</a> <a href="/blog/tags/http/" style="font-size: 13px;">http</a> <a href="/blog/tags/leetcode/" style="font-size: 13px;">leetcode</a> <a href="/blog/tags/%E4%BA%8C%E5%88%86%E6%95%B0%E7%BB%84/" style="font-size: 13px;">二分数组</a> <a href="/blog/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" style="font-size: 13px;">二叉树</a> <a href="/blog/tags/%E5%85%A8%E6%8E%92%E5%88%97/" style="font-size: 13px;">全排列</a> <a href="/blog/tags/%E5%8F%8C%E6%8C%87%E9%92%88/" style="font-size: 13.33px;">双指针</a> <a href="/blog/tags/%E5%8F%8D%E5%B0%84/" style="font-size: 13px;">反射</a> <a href="/blog/tags/%E5%93%88%E5%B8%8C%E8%A1%A8/" style="font-size: 13.67px;">哈希表</a> <a href="/blog/tags/%E5%9B%9E%E6%BA%AF%E6%B3%95/" style="font-size: 13px;">回溯法</a> <a href="/blog/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/" style="font-size: 13px;">多线程</a> <a href="/blog/tags/%E5%AD%97%E7%AC%A6%E4%B8%B2/" style="font-size: 13px;">字符串</a> <a href="/blog/tags/%E6%8E%92%E5%BA%8F/" style="font-size: 13.33px;">排序</a> <a href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 14px;">数据结构</a> <a href="/blog/tags/%E6%9D%82%E8%AE%B0/" style="font-size: 13px;">杂记</a> <a href="/blog/tags/%E6%A0%88/" style="font-size: 13px;">栈</a> <a href="/blog/tags/%E6%B3%9B%E5%9E%8B/" style="font-size: 13px;">泛型</a> <a href="/blog/tags/%E7%AE%97%E6%B3%95/" style="font-size: 13.33px;">算法</a> <a href="/blog/tags/%E8%8F%B2%E6%B3%A2%E9%82%A3%E5%88%87%E6%95%B0%E5%88%97/" style="font-size: 13.33px;">菲波那切数列</a> <a href="/blog/tags/%E9%80%92%E5%BD%92/" style="font-size: 13px;">递归</a> <a href="/blog/tags/%E9%93%BE%E8%A1%A8/" style="font-size: 13.33px;">链表</a> <a href="/blog/tags/%E9%98%9F%E5%88%97/" style="font-size: 13px;">队列</a> <a href="/blog/tags/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1/" style="font-size: 13px;">面向对象</a>
    </div>
  </div>

    
      
  <div class="widget">
    <h3 class="widget-title">Archive</h3>
    <div class="widget-body">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2021/07/">July 2021</a><span class="archive-list-count">9</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/07/">July 2020</a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/05/">May 2020</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/04/">April 2020</a><span class="archive-list-count">8</span></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2020/03/">March 2020</a><span class="archive-list-count">10</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget-body">
      <ul class="recent-post-list list-unstyled no-thumbnail">
        
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F/" class="title">二叉树的镜像</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T12:34:40.165Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%8E%92%E5%BA%8F%E7%9A%84%E9%93%BE%E8%A1%A8/" class="title">合并两个排序的链表</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T09:26:07.612Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E4%BB%8E%E5%B0%BE%E5%88%B0%E5%A4%B4%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8/" class="title">从尾到头打印链表</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T08:02:42.111Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC/" class="title">替换空格</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T06:28:22.026Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/blog/2021/07/14/%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E6%95%B0%E5%AD%97/" class="title">旋转数组的最小数字</a>
              </p>
              <p class="item-date">
                <time datetime="2021-07-14T06:12:09.184Z" itemprop="datePublished">2021-07-14</time>
              </p>
            </div>
          </li>
          
      </ul>
    </div>
  </div>
  

    
  </div>
</aside>

  
  
<main class="main" role="main">
  <div class="content">
  <article id="post-哈希表" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting">
    
    <div class="article-header">
      
        
  
    <h1 class="article-title" itemprop="name">
      哈希表
    </h1>
  

      
      <div class="article-meta">
        <span class="article-date">
    <i class="icon icon-calendar-check"></i>
	<a href="/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/" class="article-date">
	  <time datetime="2020-03-26T06:54:57.263Z" itemprop="datePublished">2020-03-26</time>
	</a>
</span>
        
        
  <span class="article-tag">
    <i class="icon icon-tags"></i>
	<a class="article-tag-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a>
  </span>


        

        <span class="post-comment"><i class="icon icon-comment"></i> <a href="/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/#comments" class="article-comment-link">Comments</a></span>
        
      </div>
    </div>
    <div class="article-entry marked-body" itemprop="articleBody">
      
        <p>哈希表又称为散列表，它可以通过把值直接映射到表中的位置来访问。这个函数叫做哈希函数。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。比较知名的散列函数MD5/SHA。查找、删除和插入时间复杂度都为O(1)。</p>
<h3 id="散列函数设计"><a href="#散列函数设计" class="headerlink" title="散列函数设计"></a>散列函数设计</h3><ul>
<li>折叠法：<br>将数据项按照位数分为若干段，再讲几段数字相加，最后对散列表大小求余，得到散列值。例如电话号码62767255，每两位相加（62+76+72+55）= 256，散列表的长度为11，求余得1。有时候折叠法还会包括隔数反转，以便得到更好的散列特性。</li>
<li>平方取中法：<br>首先将数据项做平方运算，然后去平方数中间两位，再对大小取余</li>
</ul>
<h3 id="哈希冲突"><a href="#哈希冲突" class="headerlink" title="哈希冲突"></a>哈希冲突</h3><p>如果两个数据项被散列到同一个槽，这时就发生了哈希冲突</p>
<ul>
<li>线性探测：当发生冲突时，在冲突槽逐个向后查找。缺点是可能会在冲突槽附近造成聚集。h(k)=(h’(k)+i)%M</li>
<li>二次探测法：h(k)=(h’(k)+i^2)%M</li>
</ul>

      
    </div>
    <div class="article-footer">
      <blockquote class="mt-2x">
  <ul class="post-copyright list-unstyled">
    
    <li class="post-copyright-link hidden-xs">
      <strong>本文链接：</strong>
      <a href="http://sunjinxu99.gitee.io/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/" title="哈希表" target="_blank" rel="external">http://sunjinxu99.gitee.io/blog/2020/03/26/%E5%93%88%E5%B8%8C%E8%A1%A8/</a>
    </li>
    
    <li class="post-copyright-license">
      <strong>版权声明： </strong> 本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！
    </li>
  </ul>
</blockquote>


<div class="panel panel-default panel-badger">
  <div class="panel-body">
    <figure class="media">
      <div class="media-left">
        <a href="" target="_blank" class="img-burn thumb-sm visible-lg">
          <img src="/blog/images/avatar.png" class="img-rounded w-full" alt="">
        </a>
      </div>
      <div class="media-body">
        <h3 class="media-heading"><a href="" target="_blank"><span class="text-dark">小马</span><small class="ml-1x"></small></a></h3>
        <div></div>
      </div>
    </figure>
  </div>
</div>


    </div>
  </article>
  
    
  <section id="comments">
  	
      <div id="vcomments"></div>
    
  </section>


  
</div>

  <nav class="bar bar-footer clearfix" data-stick-bottom>
  <div class="bar-inner">
  
  <ul class="pager pull-left">
    
    <li class="prev">
      <a href="/blog/2020/03/26/%E6%A0%91/" title="二叉树"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;Newer</span></a>
    </li>
    
    
    <li class="next">
      <a href="/blog/2020/03/26/%E9%98%9F%E5%88%97%E5%92%8C%E6%A0%88/" title="队列和栈"><span>Older&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a>
    </li>
    
    
  </ul>
  
  
  
  <div class="bar-right">
    
  </div>
  </div>
</nav>
  


</main>

  <footer class="footer" itemscope itemtype="http://schema.org/WPFooter">
	
    <div class="copyright">
    	
        <div class="publishby">
        	Theme by <a href="https://github.com/cofess" target="_blank"> cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.
        </div>
    </div>
</footer>
  <script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script>
<script>
window.jQuery || document.write('<script src="js/jquery.min.js"><\/script>')
</script>

<script src="/blog/js/plugin.min.js"></script>


<script src="/blog/js/application.js"></script>


    <script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: 'Posts',
            PAGES: 'Pages',
            CATEGORIES: 'Categories',
            TAGS: 'Tags',
            UNTITLED: '(Untitled)',
        },
        ROOT_URL: '/blog/',
        CONTENT_URL: '/blog/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

<script src="/blog/js/insight.js"></script>






   




   
    
  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/valine"></script>
  <script type="text/javascript">
  var GUEST = ['nick', 'mail', 'link'];
  var meta = 'nick,mail,link';
  meta = meta.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#vcomments',
    verify: false,
    notify: false,
    appId: '',
    appKey: '',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: meta,
    pageSize: '10' || 10,
    visitor: false
  });
  </script>

     







</body>
</html>